package Lee_code;

import org.omg.PortableInterceptor.INACTIVE;

import java.util.HashSet;

/**
 * @author blh
 * @date 2024年08月02日 10:34
 */
public class Lee_264_82 {

    // 创建一个质数表
    HashSet<Integer> zhiShu = new HashSet<>();

    public int nthUglyNumber(int n) {
        // 给你一个整数 n ，请你找出并返回第 n 个 丑数 。
        // 丑数 就是质因子只包含 2、3 和 5 的正整数。1也是
        int index = 1;
        int count = 0;

        while (true) {
            if (index == 1) {
                count++;
            } else if (judgeUgly(index)) {
                count++;
            }
            if (count == n) {
                return index;
            }
            index++;
        }
    }

    private boolean judgeUgly(int num) {
        int len = (int) Math.pow(num, 0.5);
        if (zhiShu.contains(num) && num > 5) {
            return false;
        } else if (judgeZhi(num) && num > 5) {
            zhiShu.add(num);
            return false;
        }

        for (int i = 2; i <= len; i++) {
            if (num % i == 0) {
                int temp = num / i;
                if (zhiShu.contains(temp)) {
                    if (temp != 2 && temp != 3 && temp != 5) {
                        return false;
                    }
                }
                else if (judgeZhi(temp)) {
                    if (temp != 2 && temp != 3 && temp != 5) {
                        return false;
                    }
                }

                if (zhiShu.contains(i)) {
                    if (i != 2 && i != 3 && i != 5) {
                        return false;
                    }
                }
                else if (judgeZhi(i)) {
                    if (i != 2 && i != 3 && i != 5) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    boolean judgeZhi(int num) {

        // 质数是只有1和本身为因子的数
        int len = (int) Math.pow(num, 0.5);
        for (int i = 2; i <= len; i++) {
            if (num % i == 0) {
                return false;
            }
        }

        return true;
    }
}
